import java.util.*;

/**
 * 797. 所有可能的路径
 * https://leetcode-cn.com/problems/all-paths-from-source-to-target/
 */
public class Solutions_797 {
    public static void main(String[] args) {
//        int[][] graph = {{1, 2}, {3}, {3}, {}};  // output: {{0, 1, 3}, {0, 2, 3}}

//        int[][] graph = {{4, 3, 1}, {3, 2, 4}, {3}, {4}, {}};
        // output: {{0, 4}, {0, 3, 4}, {0, 1, 3, 4}, {0, 1, 2, 3, 4}, {0, 1, 4}}

//        int[][] graph = {{1}, {}};  // output: {{0, 1}}

        int[][] graph = {{1, 2, 3}, {2}, {3}, {}};  // output: {{0, 1, 2, 3}, {0, 2, 3}, {0, 3}}

//        int[][] graph = {{1, 3}, {2}, {3}, {}};  // output: {{0, 1, 2, 3}, {0, 3}}

        List<List<Integer>> result = allPathsSourceTarget(graph);
        System.out.println(result);
    }

    private static List<List<Integer>> res = null;
    public static List<List<Integer>> allPathsSourceTarget(int[][] graph) {
        res = new ArrayList<>();
        if (graph[0] == null || graph[0].length < 1) {
            return res;
        }
        // 终点
        int end = graph.length - 1;
        for (int n : graph[0]) {
            // 起点为 0，从 n 开始出发，判断是否能够到达 end
            List<Integer> list = new ArrayList<>();
            list.add(0);
            list.add(n);
            dfs(n, end, list, graph);
        }
        return res;
    }

    public static void dfs(int cur, int end, List<Integer> list, int[][] graph) {
        if (cur == end) {
            // 结束条件：到达 end
            res.add(new ArrayList<>(list));
            return;
        }
        for (int n : graph[cur]) {
            // 以 cur 为起点，判断从 cur 是否可以到达 end
            list.add(n);
            dfs(n, end, list, graph);
            // 移除当前操作
            list.remove(list.size() - 1);
        }
    }
}
